//
// Created by pangy on 2025/5/11.
//

#ifndef LINKLIST_H
#define LINKLIST_H

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "Status.h"

typedef int ElemType;

// 结点类型
typedef struct LNode {
    ElemType data;
    struct LNode* next;
} LNode, *Link, *Position;

// 链表类型
typedef struct {
    Link head, tail;                // 头结点,尾结点
    int len;                        // 链表长度
} LinkList;

/* 线性表基本操作 链表实现 */


/*--------------------------------内存操作-----------------------------------*/
/**
 * 分配结点空间,创建结点p, 值为e.
 * @param p 指向结点的指针
 * @param e 结点值
 * @return OK/ERROR
 */
Status MakeNode(Link* p, ElemType e);

/**
 * 释放结点空间
 * @param p 指向结点的指针
 */
void FreeNode(Link* p);


/*---------------------------------链表常规操作------------------------*/
/**
 * 构造一个空的链表 L
 * 成功返回OK,失败返回ERROR
*/
Status InitList(LinkList* L);

/**
 * 销毁线性表
 * 成功返回OK, 失败返回ERROR
 * */
Status DestroyList(LinkList* L);

/**
 * 清空线性表, 释放原链表的节点空间
 * 成功返回OK,失败返回ERROR
*/
Status ClearList(LinkList* L);

/**
 * 线性表判空
 * 空表返回TRUE, 否则返回FALSE
 * */
Boolean ListEmpty(LinkList L);

/**
 * 线性表长度
 * 返回线性表长度, 空表返回0
 * */
int ListLength(LinkList L);

/**
 * 返回链表中第一个满足compare条件的结点
 * @param L 链表
 * @param e 数据元素值
 * @param Compare 比较函数
 * @return 结点
 */
Position LocateElem(LinkList L, ElemType e, Status (Compare)(ElemType, ElemType));

/**
 * 在指定位置之前插入数据元素
 * @param L 线性表
 * @param i 指定位置
 * @param e 插入数据元素
 * @return OK/ERROR
 */
Status ListInsert(LinkList* L, int i, ElemType e);

/**
 * 删除指定位置的数据元素
 * @param L 线性表
 * @param i 位置
 * @param e 删除的数据元素
 * @return OK/ERROR
 */
Status ListDelete(LinkList* L, int i, ElemType* e);

/**
 * 线性表数据元素依次操作
 * @param L 线性表
 * @param Visit 操作函数
 */
void ListTraverse(LinkList L, void (*visit)(ElemType));



/*-----------------------------链表扩展操作--------------------------------------*/

/**
 * head为链表头结点,将s指向结点插入到第一个结点之前
 * @param head 头结点
 * @param s 待插入结点
 * @return OK/ERROR
 */
Status InsertFirst(LinkList *L, Link s);

/**
 * head为链表头结点, 删除第一个结点并赋给q
 * @param head
 * @param q
 * @return OK/ERROR
 */
Status DeleteFirst(LinkList *L, Link* q);

/**
 * 将结点s追加到链表L末尾
 * @param L 链表
 * @param s 结点
 * @return ok/ERROR
 */
Status Append(LinkList* L, Link s);

/**
 * 删除末尾结点
 * @param L
 * @param q
 * @return
 */
Status Remove(LinkList* L, Link* q);

/**
 * 插入元素到指定结点之前
 * @param L 链表
 * @param p 指定结点
 * @param s 插入结点
 * @return
 */
Status InsertBefore(LinkList* L, Link* p, Link s);

/**
 * 插入结点到指定结点之后
 * @param L
 * @param p
 * @param s
 * @return
 */
Status InsertAfter(LinkList* L, Link* p, Link s);

/**
 * 更新结点数据域
 * @param p 结点
 * @param e 数据
 * @return OK/ERROR
 */
Status SetCurElem(Link p, ElemType e);

/**
 * 获取结点数据域
 * @param p
 * @param e
 * @return
 */
ElemType GetCurElem(Link p);

/**
 * 返回链表头结点
 * @param L
 * @return
 */
Position GetHead(LinkList L);

/**
 * 返回链表尾结点
 * @param L
 * @return
 */
Position GetLast(LinkList L);

/**
 * 返回指定结点的前驱
 * @param L
 * @param p
 * @return
 */
Position PriorPos(LinkList L, Link p);

/**
 * 返回指定结点的后继
 * @param L
 * @param p
 * @return
 */
Position NextPos(LinkList L, Link p);

/**
 * 返回链表指定索引的结点
 * @param L 链表
 * @param i 索引
 * @param p 结点
 * @return OK/ERROR
 */
Status LocatePos(LinkList L, int i, Link* p);



#endif //LINKLIST_H
